package com.example.zzy.zzytest.bit;

public class PrintOddTimesNum {

    /**
     * 一个数组中只有一个数出现了奇数次，其他数字都出现了偶数次，找到出现奇数次的数
     *
     * @param nums
     */
    public static void printOddTimesNum1(int[] nums) {
        int eor = 0;
        for (int num : nums) {
            eor = eor ^ num;
        }
        System.out.println(eor);
    }

    /**
     * 一个数组中只有两个不同的数出现了奇数次，其他数字都出现了偶数次，找到出现奇数次的数
     *
     * @param nums
     */
    public static void printOddTimesNum2(int[] nums) {
        //eor = a^b
        int eor = 0;
        for (int num : nums) {
            eor = eor ^ num;
        }
        //ab不同即a^b在某位一定是1，根据该位是1或0，可以把所有数字分成两部分
        //提取最右侧的1
        int rightOne = eor & (~eor + 1);

        //将rightOne这一位为1的数字全异或起来，得到其中一个数
        int a = 0;
        for (int num : nums) {
            if ((num & rightOne) == 0) {
                a = a ^ num;
            }
        }

        //继续通过异或算出另一个数
        int b = eor ^ a;
        System.out.println(a + "," + b);
    }

    public static void main(String[] args) {
        int[] nums1 = new int[]{1, 1, 2, 2, 2, 3, 3, 3, 3};
        printOddTimesNum1(nums1);

        int[] nums2 = new int[]{1, 1, 2, 2, 2, 3, 3, 4, 3, 3};
        printOddTimesNum2(nums2);
    }
}
